package sjjg.tree;

public class HeapSort {

    //判断heap中两位置的大小
    public boolean less(Comparable[] heap,int index1,int index2){
        return heap[index1].compareTo(heap[index2])<0;
    }
    //交换heap中两索引处的值
    public void exchange(Comparable[]heap,int index1,int index2){
        Comparable temp;
        temp=heap[index1];
        heap[index1]=heap[index2];
        heap[index2]=temp;
    }
    //根据原数组source构建出堆
    Comparable[] createHeap(Comparable[]source){
        Comparable[] heap = new Comparable[source.length + 1];//废弃索引0
        //将原数组拷贝到无序堆中
        System.arraycopy(source,0,heap,1,source.length);
        //对堆进行处理使之成为有序堆(这里对堆的1/2处开始下沉处理 使堆有序)
        int k=(heap.length-1)/2;
        while (k>=1){
            //堆的1/2处开始下沉 知道第一个元素完成下沉
            sink(heap,k,heap.length-1);
            k--;
        }
        return heap;
    }
    //对source数组进行堆排序
    public void heap_sort(Comparable[]source){
        Comparable[] heap = createHeap(source);
        //进行排序(将每次的第一个元素放在无序的索引最大处)
        int N=heap.length-1;
        while (N>1){
            exchange(heap,1,N);//交换最大值与堆最大索引处的值(有序的地方已经被剔除堆外)
            N--;//堆大小--;
            sink(heap,1,N);//使堆重新有序
        }
        System.arraycopy(heap,1,source,0,heap.length-1);//使原数组有序
    }
    //在heap堆中对target元素做下沉 范围是0~range
    public void sink(Comparable[]heap,int target,int range){
                int max=0;//用来记录较大位置的索引
                while(2*target<=range){
                     //判断是否有右子节点
                    if(2*target+1<=range){
                        //判读左右节点的大小
                        if(less(heap,2*target,2*target+1)){
                            max=2*target+1;
                        }else {
                            max=2*target;
                        }
                    }else {
                        max=2*target;
                    }
                    if(less(heap,target,max)){
                        exchange(heap,target,max);
                    }else {
                        break;//此元素下沉结束
                    }
                    target=max;//进行下一次下沉
                }
    }

    public static void main(String[] args) {
        HeapSort heapSort = new HeapSort();
        Integer []source={3,2,7,8,7,4,9,3,1,5,11,4,7,8,1,99,44,88};
        heapSort.heap_sort(source);
        for (Integer integer : source) {
            System.out.print(integer+" ");
        }
    }

}
